package leetcode.map;

import java.util.*;

public class Lc1466 {

    public static int minReorder(int n, int[][] connections) {
        HashMap<Integer, List<Integer>> next = new HashMap<>();
        HashMap<Integer, List<Integer>> pre = new HashMap<>();

        for (int i = 0; i < connections.length; i++) {
            int u = connections[i][0];
            int v = connections[i][1];
            List<Integer> list1 = next.getOrDefault(u, new ArrayList<>());
            list1.add(v);
            next.put(u, list1);
            List<Integer> list2 = pre.getOrDefault(v, new ArrayList<>());
            list2.add(u);
            pre.put(v, list2);
        }
        int ans = 0;
        int cnt = 1;
        boolean[] visted = new boolean[n];
        visted[0] = true;
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        List<Integer> list = pre.get(0);
        if (list != null) {
            for (int u : list) {
                queue.offerLast(u);
                visted[u] = true;
                cnt++;
            }
        }
        list = next.get(0);
        if (list != null) { //把1所有的后继节点反向
            for (int u : list) {
                queue.offerLast(u);
                visted[u] = true;
                ans++;
                cnt++;
            }
        }
        if (cnt == n) return ans;
        while (!queue.isEmpty()) {
            int u = queue.pollFirst();
            list = pre.get(u); //所有的前期节点都可以到达0
            if (list != null) {
                for (int v : list) {
                    if (visted[v]) continue;
                    queue.offerLast(v);
                    visted[v] = true;
                    cnt++;
                }
            }
            list = next.get(u);
            if (list != null) {
                for (int v : list) {
                    if (visted[v]) continue;
                    queue.offerLast(v);
                    visted[v] = true;
                    ans++;
                    cnt++;
                }
            }
            if (cnt == n) return ans;
        }
        return ans;
    }

    public static void main(String[] args) {
        int n = 6;
        int[][] connections = {{0,1},{1,3},{2,3},{4,0},{4,5}};
        System.out.println(minReorder(n, connections));

    }


}
